/**
 * https://leetcode-cn.com/problems/squares-of-a-sorted-array/
 * 有序数组的平方
 * @param nums 
 */
const sortedSquares = (nums: number[]): number[] => {
    const len = nums.length;
    const arr: number[] = new Array(len).fill(0);

    // 1. 找到分界线
    let divide = -1;
    for (let i = 0; i < len; i++) {
        // 找到比0大的项
        if (nums[i] >= 0) {
            divide = i;
            break;
        }
    }

    // 分界线是-1, 那么说明都是负数
    // 分界线是0, 说明都是正数
    if (divide === -1 || divide === 0) {
        for (let i = 0; i < len; i++) {
            arr[i] = nums[i] ** 2;
        }

        return divide === 0 ? arr : arr.reverse();
    }



    // 2. 右边数组平方, 是依次递增的
    for (let i = divide; i < len; i++) {
        arr[i] = nums[i] ** 2;
    }

    // 3. 分界线左边的先平方
    for (let i = 0; i < divide; i++) {
        arr[i] = nums[i] ** 2;
    }




    // 左边先平方
    for (let i = 0; i < divide; i++) {
        arr[i] = nums[i] ** 2;
    }

    // 4. 分界线左边是降序的, 右边是升序的, 合并
    // 拷贝左边数组并反转
    const leftArr = arr.slice(0, divide);

    let ai = 0,
        li = 0,
        le = divide,
        ri = divide,
        re = len;


    while (li < le && ri < re) {

        if (arr[ri] < leftArr[le - 1]) {
            // 右边 < 左边
            arr[ai] = arr[ri++]

        } else {
            // 右边 >= 左边
            arr[ai] = leftArr[--le]
        }
        ai++
    }

    // 右边先结束
    if (ri >= re) {
        // 将左边的拷贝到数组中
        for (let i = le - 1; i >= li; i--) {
            arr[ai++] = leftArr[i]
        }
    }


    return arr;
};


const sortedSquares5 = (nums: number[]): number[] => {
    const len = nums.length;
    const arr: number[] = new Array(len).fill(0);

    // 从后往前遍历
    let i = 0,
        j = len - 1,
        index = len - 1;

    while (i <= j) {
        // 前后比较
        let left = nums[i] * nums[i],
            right = nums[j] * nums[i];

        if (left < right) {
            // 右边比较大
            arr[index--] = right;
            j--;
        } else {
            // 左边比较大
            arr[index--] = left;
            i++;
        }
    }
    return arr;
};


const sortedSquares4 = (nums: number[]): number[] => {
    const len = nums.length;
    const arr: number[] = [];

    // 从后往前遍历
    let i = 0,
        j = len - 1;

    while (i <= j) {
        // 前后比较
        let left = nums[i] ** 2,
            right = nums[j] ** 2;

        if (left < right) {
            // 右边比较大
            arr.push(right);
            j--;
        } else {
            // 左边比较大
            arr.push(left)
            i++;
        }
    }
    return arr.reverse();
};


const sortedSquares2 = (nums: number[]): number[] => {
    const len = nums.length;
    const arr: number[] = new Array(len).fill(0)

    // 从后往前遍历
    for (let i = len - 1; i >= 0; i--) {
        const n = nums[i] ** 2

        // 负数才需要调整
        if (nums[i] < 0) {
            // 找到应该要插入的位置
            let inserted = i;
            for (let j = i + 1; j < len; j++) {
                if (n > arr[j]) {
                    // 待插入的位置
                    inserted = j;
                }
            }

            // 待插入的位置找到了
            console.log(inserted, i)
            if (inserted !== i) {
                // 移动元素
                for (let k = i; k < inserted; k++) {
                    arr[k] = arr[k + 1]
                }

                // 元素插入的位置
                arr[inserted] = n
                // 进入下一轮
                continue
            }

        }
        // else {
        arr[i] = n;
        // }
        console.log(arr)
    }

    return arr;
};


const sortedSquares3 = (nums: number[]): number[] => {
    const len = nums.length;
    const arr: number[] = new Array(len).fill(0)

    // 从后往前遍历
    for (let i = len - 1; i >= 0; i--) {
        arr[i] = nums[i] ** 2;
    }
    arr.sort((a, b) => a - b)
    return arr;
};

const array = [0, 2, 3, 4]
// const array = [-5, -3, -2, -1]
// const array = [-4, -1, 0, 3, 10]
console.log(sortedSquares(array));